/*
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/submissions/584675843/?envType=problem-list-v2&envId=dynamic-programming
121. 买卖股票的最佳时机
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp[100001]={0},ans=0,i,leng=prices.size();
        dp[0]=prices[0];
        for(i=1;i<leng;++i){
            dp[i]=min(dp[i-1],prices[i]);
        }
        for(i=0;i<leng;++i){
                if(prices[i]-dp[i]>ans){
                    ans=prices[i]-dp[i];
                }
            }
        return ans;
    }
};